//这个是不考虑流量的版本，打印路线暂无问题

#include <iostream>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;
int **roadlength;
int **restrictions;
int **cars;
int N,M;//N是地点数量，M是车数量
//所有出现的坐标都是默认从1开始计数，因此在二维数组中要减一
/*class route{
    public:
    int* stops;
    int length;
    route():stops(),length(0){
        this->stops = new int[N];
    };
    route(int start):stops(),length(0){
        this->stops = new int[N];
        this->stops[0]=start;
        this->length=0;//TODO：应该是0还是INT_MAX？
    }
    route(int start,int next,int length):stops(),length(length){
        this->stops = new int[N];
        this->stops[0]=start;
        this->stops[1]=next;
        this->length=length;
    }
    route(vector<int> stops,int length):stops(),length(length){
        this->stops = new int[N];
        for (int i=0;i<stops.size();i++)this->stops[i]=stops[i];
        this->length=length;
    };
};
*/
int A2B_straight(int A, int B){
    return roadlength[A-1][B-1];
}
/*
route *fromAminRoad(int A){
    route *routes=(route *)malloc(N*sizeof(route));//TODO:应该使用vector还是数组？->使用malloc
    bool *S=new bool[N];
    int path[N];
    int distance[N];
    for (int i=1;i<=N;i++){
        distance[i-1]= A2B_straight(A,i);
        S[i]=false;
        if (i!=A&&distance[i-1]<INT_MAX)path[i-1]=A;
        else path[i-1]=-1;
    } 
    
    S[A]=true;
    distance[A]=0;
    for (int i=0;i<N-1;i++){
        int min=INT_MAX;
        int stop=A;
        for (int j=1;j<=N;j++){
            if (!S[j-1]&&distance[j-1]<min){
                min=distance[j-1];
                stop=j;
            }
        }
        S[stop-1]=true;
        for (int k=1;k<=N;k++){
            int length2=A2B_straight(A,k);
            if (!S[k-1]&&length2<INT_MAX&&distance[stop-1]+length2<distance[k-1]){
                distance[k-1]=distance[stop-1]+length2;
                path[k-1]=stop;
            }
        }
    }
    //产生路径用于存储

    for (int i=1;i<=N;i++){
        if (i==A){
            routes[i-1]=route(A);
        }
        else{
            vector<int> temp;
            int p=i;
            while(p!=A&&p!=-1){
                temp.push_back(p);
                if (p!=-1&&p!=0)p=path[p-1];
                else break;//防止p=0
            }
            temp.push_back(A);
            reverse(temp.begin(),temp.end());
            printf(" %d ",distance[i-1]);
            routes[i-1]=route(temp,distance[i-1]);
            
        }
    }
    return routes;
}
*/
void fromAminRoad(int A,int distance[],int path[]){
    //route *routes=(route *)malloc(N*sizeof(route));//TODO:应该使用vector还是数组？->使用malloc
    bool S[N];
    
    //int distance[N];
    for (int i=1;i<=N;i++){
        distance[i-1]= A2B_straight(A,i);
        //printf("%d ",distance[i-1]);
        S[i-1]=false;
        if (i!=A&&distance[i-1]<INT_MAX)path[i-1]=A;
        else path[i-1]=-1;
    } 
    
    S[A-1]=true;
    distance[A-1]=0;


    for (int i=0;i<N-1;i++){
        int min=INT_MAX;
        int stop=A;
        for (int j=1;j<=N;j++){
            //printf("%d ",distance[j-1]);
            if (!S[j-1]&&distance[j-1]<min){
                min=distance[j-1];
                stop=j;
            }
        }
        S[stop-1]=true;
        for (int k=1;k<=N;k++){
            int length2=A2B_straight(stop,k);
            //printf("%d\n",length2);
            if (!S[k-1]&&length2<INT_MAX&&distance[stop-1]+length2<distance[k-1]){
                distance[k-1]=distance[stop-1]+length2;
                path[k-1]=stop;
            }
        }
        //printf("\n");
        //for (int m=0;m<N;m++){printf("%d ",distance[m]);}
        //printf("\n");
        //for (int m=0;m<N;m++){printf("%d ",path[m]);}
        //printf("\n");
    }
    
}
void the_shortest_path(int A,int B,int distance[],int path[]){
    int temp[N];
    int count=0;
    while (B!=A){
        temp[count]=B;
        //printf("%d ",B);
        B=path[B-1];
        count++;
    }
    temp[count]=A;
    count++;
    while (count>0){
        cout<<temp[count-1];
        if (count!=1)cout<<" ";
        count--;
    }
    cout<<endl;
    return;
}
/*
int searchonecar(int start, int stop){
    route *routes=fromAminRoad(start); 
    for (int i=0;i<N;i++){
        cout<<routes[stop-1].stops[i];
        if (routes[stop-1].stops[i]!=stop)cout<<" ";
        else{break;}
    }
    cout<<endl;
    delete[] routes;
    int length=routes[stop-1].length;
    return length;
}
*/
int searchonecar(int start, int stop){
    int distance[N],path[N];

    fromAminRoad(start,distance,path); 
    the_shortest_path(start,stop,distance,path);
    return distance[stop-1];
}
int searchallcars(){
    int sum=0;
    for (int i=0;i<M;i++){
        sum+=searchonecar(cars[i][0], cars[i][1]);
        //printf("\n%d\n",sum);
    }
    return sum;
}
int main(){
    
    cin>>N>>M;
    roadlength=new int*[N];
    restrictions=new int*[N];
    cars=new int*[M];
    for (int i=0;i<N;i++){
        roadlength[i]=new int[N];
        for (int j=0;j<N;j++){
            cin>>roadlength[i][j];
            if (roadlength[i][j]==0&&i!=j)roadlength[i][j]=INT_MAX;
        }
    }
    /*for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            cout<<roadlength[i][j];  
        }
    }//print调试*/
    //int a=1;
    for (int i=0;i<N;i++){
        restrictions[i]=new int[N];
        for (int j=0;j<N;j++){
            cin>>restrictions[i][j];
        }
    }
    //int b=1;
    for (int i=0;i<M;i++){
        cars[i]=new int[2];
        cin>>cars[i][0]>>cars[i][1];
    }
    //int c=1;
    int sum=searchallcars();
    cout<<sum<<endl;
    
    return 0;
}